package offer;

public class offerII_0101 {
    public boolean canPartition(int[] nums) {
        int len=nums.length;
        int sum=0;
        int max=0;
        for(int i=0;i<len;++i){
            sum+=nums[i];
            max=Math.max(max,nums[i]);
        }
        if(len<2) return false;
        if(sum%2==1) return false;
        if(max>sum/2) return false;
        if(max==sum/2) return true;
        boolean[][] dp=new boolean[len][sum/2+1];
        for(int i=0;i<len;++i){
            dp[i][0]=true;
        }
        dp[0][nums[0]]=true;
        for(int i=1;i<len;++i){
            for(int j=1;j<sum/2+1;++j){
                if(nums[i]>j){
                    dp[i][j]=dp[i-1][j];
                }
                else dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
            }
        }
        return dp[len-1][sum/2];
    }
}
